﻿#define _CRT_SECURE_NO_WARNINGS 1
给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。



示例 1：

输入：[1, 2, 3, 4, 5]
输出：此列表中的结点 3 (序列化形式：[3, 4, 5])
返回的结点值为 3 。(测评系统对该结点序列化表述是[3, 4, 5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：

输入：[1, 2, 3, 4, 5, 6]
输出：此列表中的结点 4 (序列化形式：[4, 5, 6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。


提示：

给定链表的结点数介于 1 和 100 之间。

来源：力扣（LeetCode）
链接：https ://leetcode-cn.com/problems/middle-of-the-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 //法1：先查个数，再找中间位置，相当于遍历两次，性能不是很好
    struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* cur = head;
    int i = 0;
    while (cur)
    {
        cur = cur->next;
        i++;
    }
    int mid = 0;
    struct ListNode* newHead = head;
    while (newHead && mid < i / 2)
    {
        mid++;
        newHead = newHead->next;
    }
    return newHead;

}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 //法2：快慢指针，遍历一次，快指针一次两步，慢指针一次一步
struct ListNode* middleNode(struct ListNode* head) {
    if (head->next == NULL)
        return head;
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)//这里必须先fast再fast->next
    {//因为当链表为数目为偶数时，循环最后一次已经超过，fast为空，fast->next是错误的指向
     //故把fast先放前面，不满足时就不会执行到fast->next,这是&&运算符的特征：前者为假，就不继续判断
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;

}
